#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INCREATMENT 10
#define MAX_SIZE 100
typedef int Status;
typedef int SElemType;

typedef struct QNode
{
    struct QNode *next; // 链表下一项
    SElemType data;     // 链表数据
} QNode;

typedef struct LinkQueue
{
    QNode *front; // 头节点
    QNode *rear;  // 尾节点
} LinkQueue;

Status init_queue(LinkQueue *queue)
{
    // 定义一个头节点
    queue->front = queue->rear = (QNode *)malloc(sizeof(QNode));
    if (!queue->front)
    {
        return ERROR;
    }
    queue->front->next = NULL; // 初始化头节点
    return OK;
}

Status insert_queue(LinkQueue *queue, SElemType e) // 把e尾插进队列
{
    // 尾插
    QNode *head_node = (QNode *)malloc(sizeof(QNode));
    if (!head_node)
    {
        return ERROR;
    }
    head_node->next = NULL;        // 初始化节点
    head_node->data = e;           // 给节点赋值
    queue->rear->next = head_node; // 让他在最后
    queue->rear = head_node;       // 调整尾指针的指向
    return OK;
}

Status destroy_queue(LinkQueue *queue) // destory队列,并输出队列的值
{
    while (queue->front) // 队列不空
    {
        queue->rear = queue->front->next;
        free(queue->front);
        queue->front = queue->rear;
        if (queue->rear)
        {
            printf("%d ", queue->rear->data);
        }
    }
}

Status delete_queue(LinkQueue *queue, SElemType *e) // destory and return data
{
    // 删除第一个值,使用e返回这个值
    if (queue->front == queue->rear)
    {
        *e = -1; //*e为-1代表队列已空
        return ERROR;
    }
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node = queue->front->next;       // 取得队列第一个节点
    queue->front->next = node->next; // 头节点指向下一个节点
    *e = node->data;                 // 取值
    node->next = NULL;               // 断开node与后续节点;
    if (node == queue->rear)
    {
        queue->front = queue->rear;
    }
    free(node);
}

Status is_empty(LinkQueue *queue)
{
    if (queue->front == queue->rear)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}
int main()
{
    // 定义一个队列结构体
    LinkQueue *Queue = (LinkQueue *)malloc(sizeof(LinkQueue));

    // 初始化队列
    init_queue(Queue);

    // 插入值
    for (int i = 1; i < 10; i++)
    {
        insert_queue(Queue, i);
    }
    // destory队列,并输出队列的值
    printf("第一次构造的队列值为:");
    destroy_queue(Queue);
    // 重新构造队列
    init_queue(Queue);
    for (int i = 9; i > 0; i--)
    {
        insert_queue(Queue, i);
    }
    printf("\n");
    // 9 8 7 6 5 4 3 2 1
    printf("第二次构造队列的初始值:9 8 7 6 5 4 3 2 1\n");
    //  删除第一个值,返回删除的值
    SElemType *e = (SElemType *)malloc(sizeof(SElemType));
    for (int i = 0; i < 15; i++)
    {
        delete_queue(Queue, e);
        printf("删除第%d个元素:%d\n", i, *e); //*e为-1代表队列已空
    }
    printf("\n");
    // 判断队列是否空
    printf("队列是否为空:%d\n", is_empty(Queue)); // 1是TRUE,2是FALSE

    return 0;
}